package org.example;

import java.util.HashMap;
import java.util.Map;

public class Test1 {
    //leetcode 只出现一次的数字II
    //https://leetcode.cn/problems/single-number-ii/description/?envType=problem-list-v2&envId=array

    /**
     * 哈希记录每个元素出现的次数
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> hash = new HashMap<>();
        for (int n : nums) {
            hash.put(n,hash.getOrDefault(n,0) + 1);
        }
        for (Map.Entry<Integer,Integer> entry : hash.entrySet()) {
            int key = entry.getKey(), value = entry.getValue();
            if (value == 1) return key;
        }
        return -1;
    }

    /**
     * 位运算，只出现一次的元素的对应的bit位为数组中所有元素对应bit位的和MOD3
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        //因为除了答案出现了一次之外，其他的元素都出现了三次，那么在32个bit位上
        //答案的每一个就为数组所有元素的对应bit位的和%3
        //例如 2 2 2 3
        //10 10 10 11
        //只出现一次的数字的0位为 (0+0+0+1)%3=1
        //第1位为(1+1+1+1)%3=1
        //所以只出现一次的元素为11 = 3
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int n : nums) {
                sum += (n >> i) & 1;
            }
            ret ^= (sum % 3) << i;
        }
        return ret;
    }
}
